package data_structure.mooc;

import data_structure.helper.ArrayGenerator;
import data_structure.helper.SortingHelper;
import data_structure.helper.SwapArray;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {

    private static Random random = new Random ();

    private QuickSort() {


    }

    public static <E extends Comparable<E>> void sort(E arr[]){
        Random random = new Random();
        sort(random,arr,0,arr.length-1);
    }
    private static <E extends Comparable<E>> void sort(Random random,E arr[],int left,int right){
        if(left>=right)return;
        int partition=partition (random,arr,left,right);
        if(left<partition){
            sort (random, arr, left, partition-1);
        }
        if(right>partition){
            sort(random, arr, partition+1, right);
        }
    }

    private static <E extends Comparable<E>> int partition(Random random,E arr[],int left,int right){

        //[0,right]
        int partition=left+random.nextInt(right-left+1);
        SwapArray.swap (arr,left,partition);

        int j=left;//记录大于arr[left]元素的位置
        //[left,partition],[partition+1,right]
        for(int i=left+1;i<=right;i++){

            if(arr[i].compareTo (arr[left])<=0){
                //保持变量j的同步
                j++;
                SwapArray.swap (arr,j,i);
            }
        }
        SwapArray.swap (arr,left,j);
        return j;
    }


    /**
     * 双路快速排序：解决数组元素中含有大量的重复元素
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>>void sort2Ways(E []arr){
        sort2Ways (arr,0,arr.length-1);
    }
    public static <E extends Comparable<E>> void sort2Ways(E []arr,int left,int right){
        if(left>=right)return;
        int partition=partition2Ways (arr,left,right,random);
        sort2Ways (arr,left,partition-1);
        sort2Ways (arr,partition+1,right);
    }

    private static <E extends Comparable<E> > int partition2Ways(E []arr,int left,int right,Random random){
        int partition=left+random.nextInt (right-left+1);
        SwapArray.swap (arr,left,partition);
        int i=left+1;//左边
        int j=right;//右边
        while(true){

            while(i<=j&&arr[i].compareTo (arr[left])<0){
                i++;
            }
            while(j>=i&&arr[j].compareTo(arr[left]) >0){
                j--;
            }
            if(i>=j)break;
            SwapArray.swap (arr,i,j);
            i++;
            j--;
        }
        SwapArray.swap (arr,left,j);
        return j;
    }

    /**
     * 三路快速排序：进一步解决数组元素全部相等的情况，可以将时间复杂度优化为o(n)
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>>void sort3Ways(E []arr){
        sort3Ways (arr,0,arr.length-1);
    }
    public static <E extends Comparable<E>> void sort3Ways(E []arr,int left,int right){
        if(left>=right)return;
        int partition=left+random.nextInt (right-left+1);
        SwapArray.swap (arr,left,partition);
        int i=left+1;//用来遍历元素
        int lt=left;//第一部分元素的右边界
        int gt=right+1;//第三部分元素的左边界
        //将数组划分为三部分
        //[left+1,lt],[lt+1,i-1],[gt,right]
        while(i<gt){

            if(arr[i].compareTo (arr[left])<0){
                lt++;//在第一部分空出一个位置
                SwapArray.swap (arr,lt,i);//和当前值交换
                i++;//遍历下一个元素
            }else if(arr[i].compareTo(arr[left]) > 0){
                gt--;//在第三部分空出一个位置
                SwapArray.swap(arr, gt, i);//和当前值交换
                //注意此时不应该i++，原因在于此时对数组进行了三次划分
            }else{
                i++;
            }
        }
        SwapArray.swap (arr,left,lt);
        //递归调用函数
        //分别对两部分排序
        //[left,lt-1],[gt,right]
        sort3Ways (arr,left,lt-1);
        sort2Ways (arr,gt,right);
    }

    public static void main(String[] args) {
//        Integer []arr= ArrayGenerator.generateNormalArray (100000,100000);
//        Integer []arr2=Arrays.copyOf(arr, arr.length);
//        System.out.println("普通数组");
//        SortingHelper.testSorting (arr, "quickSort");
//        SortingHelper.testSorting (arr2,"quickSort3");
//        System.out.println("特殊数组");
        Integer []arr3=ArrayGenerator.generateNormalArray (100000,10000);
        Integer []arr4=Arrays.copyOf (arr3,arr3.length);
        SortingHelper.testSorting (arr3, "quickSort");
        SortingHelper.testSorting (arr4,"quickSort2");

    }
}
